//方法一：排序
int val;//全局变量

int cmp1(const void *pa, const void *pb){
    if(abs(*(int*)pa - val) != abs(*(int*)pb - val))
        return abs(*(int*)pa - val) - abs(*(int*)pb - val);
    else
        return *(int*)pa - *(int*)pb;
}//按与x差值的大小排序

int cmp2(const void *pa, const void *pb){
    return *(int*)pa - *(int*)pb;
}//前k个按本身大小排序

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
    val = x;
    int *ans = (int*)malloc(sizeof(int)*k);
    *returnSize = k;

    qsort(arr, arrSize, sizeof(int), cmp1);
    qsort(arr, k, sizeof(int), cmp2);

    for(int i = 0; i < k; i++){
        ans[i] = arr[i];
    }

    return ans;
}

//方法二：二分查找 + 双指针
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int Finding(int *arr,  int arrSize, int target){
    int left = 0, right = arrSize - 1, mid;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(arr[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return left;//小于x的个数，也刚好是大于等于x首元素的下标
}

int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
    int right = Finding(arr, arrSize, x);
    int left = right - 1;

    while(k--){
        if(left < 0){
            right++;
        }else if(right >= arrSize){
            left--;
        }else if(x - arr[left] <= arr[right] - x){
            left--;
        }else{
            right++;
        }
    }
    *returnSize = right - left - 1;//区间[left + 1, right - 1]即为所求，可画图辅助理解
    int *ans = (int*)malloc(sizeof(int) * (*returnSize));
    memcpy(ans, arr + left + 1, sizeof(int) * (*returnSize));
    return ans;
}

/*给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。

返回的结果必须要是按升序排好的。整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者|a - x| == |b - x| 且 a < b*/